package com.example.leetcode.trainingcamp.week5.Thursday;

/**
 * 面试题 10.05. 稀疏数组搜索 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
 *
 * <p>示例1:
 *
 * <p>输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta" 输出：-1
 * 说明: 不存在返回-1。 示例2:
 *
 * <p>输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball" 输出：4
 */
public class Offer10_05 {

    public int findString(String[] words, String s) {
        int high = words.length-1;
        int low = 0;
        int result = -1;
        while (low<=high){
            int mid = low + (high -low) /2 ;
            if (words[mid].equals(s)) return mid;
            if (!words[mid].equals("") && words[mid].compareTo(s) < 0) low = mid +1;
            if (!words[mid].equals("") && words[mid].compareTo(s) > 0) high = mid -1;
            if (words[mid].equals("")){
                int i = mid -1;
                while (i>=0){
                    if (!words[i].equals("")){
                        break;
                    }
                    i--;
                }
                if ( i == -1){
                    low = mid +1;
                }else if (words[i].compareTo(s) < 0){
                    low = mid +1;
                }else if (words[i].compareTo(s) > 0){
                    high =mid -1;
                }else {
                    return i;
                }
            }
        }
        return result;
    }
}


class TestOffer10_05{
  public static void main(String[] args) {
    String[] words = new String[]{"at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""};
    String s = "ball";
    Offer10_05 o = new Offer10_05();
    System.out.println(o.findString(words, s));
  }
}